package com.yanceysong.codetop.s41_s50;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Arrays;


public class S46_Hard_239_滑动窗口最大值 {

    /* ============================ 方法1：O(n) 单调队列 ============================ */

    /**
     * @ClassName S46_Hard_239_滑动窗口最大值
     * @Description 滑动窗口最大值问题两种解法：暴力 + 单调队列
     * @Author yanceysong
     * <p>
     * 题目链接: https://leetcode.cn/problems/sliding-window-maximum/
     * ----------------------------------------------------------------------
     * 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到最右侧。
     * 你只能看到窗口中的 k 个数字，每次滑动窗口只向右移动一位。
     * 返回每次窗口移动后得到的最大值。
     * <p>
     * 示例 1:
     * 输入: nums = [1,3,-1,-3,5,3,6,7], k = 3
     * 窗口变化及最大值：
     * .  [1, 3, -1] -3  5  3  6  7  -> 3
     * .   1 [3, -1, -3] 5  3  6  7  -> 3
     * .   1  3 [-1, -3, 5] 3  6  7  -> 5
     * .   1  3  -1 [-3, 5, 3] 6  7  -> 5
     * .   1  3  -1  -3 [5, 3, 6] 7  -> 6
     * .   1  3  -1  -3  5 [3, 6, 7] -> 7
     * 输出: [3,3,5,5,6,7]
     * <p>
     * 示例 2:
     * 输入: nums = [1], k = 1
     * 输出: [1]
     * <p>
     * 约束：
     * 1 <= k <= nums.length <= 10^5
     * -10^4 <= nums[i] <= 10^4
     * ----------------------------------------------------------------------
     * 解题思路总览：
     * 1. 暴力枚举 (Brute Force) O(n * k)
     * .   - 对每一个长度为 k 的窗口都遍历一遍，取最大值。
     * .   - 适合理解题意，不适合大数据量（会超时）。
     * 2. 单调队列 (Monotonic Queue / Deque) O(n)
     * .   - 维护一个"下标"双端队列，队列内对应的 nums 值严格单调递减。
     * .   - 队首始终是当前窗口的最大值的下标。
     * ----------------------------------------------------------------------
     * 单调队列维护规则：
     * 1. 新元素入队前：弹出队尾所有 <= 新元素值 的下标，保证值单调递减。
     * 2. 插入下标 i。
     * 3. 如果队首下标已经滑出窗口 (index <= i - k) 则弹出队首。
     * 4. 当 i >= k - 1 时，记录当前窗口最大值 = nums[deque.peekFirst()]。
     * <p>
     * ASCII 图解 (示例数组: [1,3,-1,-3,5,3,6,7], k=3)：
     * i=0, num=1  deque: [0]              (值: [1])                (窗口未成型)
     * i=1, num=3  弹出0(1 <= 3) -> 入1 -> deque: [1]            (值: [3])
     * i=2, num=-1 直接入 -> deque: [1,2]   (值: [3,-1]) 窗口[0,2] 输出3
     * i=3, num=-3 直接入 -> deque: [1,2,3] (值: [3,-1,-3]) 过期? 1<=3-3? 否 输出3
     * i=4, num=5  弹出3(-3),2(-1),1(3) -> 入4 -> deque:[4]     输出5
     * i=5, num=3  入5 -> deque:[4,5]                              输出5
     * i=6, num=6  弹5(3),4(5) -> 入6 -> deque:[6]               输出6
     * i=7, num=7  弹6(6) -> 入7 -> deque:[7]                    输出7
     * <p>
     * 关键洞察：
     * - 单调队列里的元素“候选最大值”是懒惰淘汰的：只有当它离开窗口范围或者被更大的值挤掉时才移除。
     * - 通过维护“下标”而不是“值”，可以同时判断是否过期和获取真实值。
     * - 每个元素最多入队一次、出队一次 => O(n)。
     * <p>
     * 边界处理：
     * - 如果 nums 为 null 或长度为 0，返回空数组。
     * - k == 1 时结果就是原数组副本。
     * - k == nums.length 时结果就是全局最大值。
     * <p>
     * 复杂度分析：
     * - 暴力：时间 O(n*k)，空间 O(1)
     * - 单调队列：时间 O(n)，空间 O(k)（最坏情况下队列容纳 k 个下标）
     */
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) {
            return new int[0];
        }
        int length = nums.length;
        if (k == 1) { // 每个窗口只有一个元素，直接返回副本（避免后续逻辑开销）
            return Arrays.copyOf(nums, length);
        }
        int outputLen = length - k + 1; // 结果数组长度 = 可形成的窗口个数
        int[] windowMax = new int[outputLen];
        // 双端队列存放“下标”，保证对应值严格单调递减 => 队首始终是当前窗口最大值下标
        Deque<Integer> candidateIdxDeque = new LinkedList<>();

        for (int rightIdx = 0; rightIdx < length; rightIdx++) {
            // 1. 维护队尾：若当前值 >= 队尾下标对应的值，则队尾出队
            // 这样可以确保队列中下标对应的值保持严格递减，从而队首永远是最大值的下标
            while (!candidateIdxDeque.isEmpty() && nums[rightIdx] >= nums[candidateIdxDeque.peekLast()]) {
                candidateIdxDeque.pollLast();
            }
            // 2. 插入当前元素下标到队尾
            candidateIdxDeque.offerLast(rightIdx);

            // 3. 计算当前窗口左边界（含）
            int leftIdx = rightIdx - k + 1;
            //    如果队首下标已经滑出窗口（< leftIdx）则弹出
            if (candidateIdxDeque.peekFirst() != null && candidateIdxDeque.peekFirst() < leftIdx) {
                candidateIdxDeque.pollFirst();
            }

            // 4. 当窗口长度达到 k (rightIdx >= k-1) 时，记录当前窗口最大值
            if (rightIdx >= k - 1) {
                windowMax[leftIdx] = nums[candidateIdxDeque.peekFirst()];
            }
        }
        return windowMax;
    }

    /* ============================ 方法2：O(n*k) 暴力枚举 ============================ */

    /**
     * 暴力方法：对每个窗口线性扫描找最大值
     * 用于对比与验证单调队列结果的正确性
     */
    public int[] maxSlidingWindowBruteForce(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) {
            return new int[0];
        }
        int length = nums.length;
        int[] windowMax = new int[length - k + 1];
        for (int left = 0; left + k <= length; left++) {
            int right = left + k - 1;
            windowMax[left] = findMaxInRange(nums, left, right);
        }
        return windowMax;
    }

    /**
     * 在区间 [l, r] 内线性扫描获取最大值
     */
    private int findMaxInRange(int[] nums, int l, int r) {
        int maxIndex = l;
        for (int i = l + 1; i <= r; i++) {
            if (nums[i] > nums[maxIndex]) {
                maxIndex = i;
            }
        }
        return nums[maxIndex];
    }

    /* ============================ 兼容旧命名（保留原方法） ============================ */

    /**
     * 原始类里的 maxSlidingWindow 名称对应的是暴力，这里用优化版替换；
     * 旧的暴力实现已迁移到 maxSlidingWindowBruteForce。
     */
    public int[] maxSlidingWindow1(int[] nums, int k) {
        return maxSlidingWindow(nums, k); // 兼容保留
    }

    /* ============================ 测试代码 ============================ */
    public static void main(String[] args) {
        S46_Hard_239_滑动窗口最大值 solution = new S46_Hard_239_滑动窗口最大值();
        System.out.println("=== 滑动窗口最大值 测试开始 ===\n");

        // 基础功能 / 边界 / 典型模式
        testCase(solution, new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3, new int[]{3, 3, 5, 5, 6, 7}, "示例1");
        testCase(solution, new int[]{1}, 1, new int[]{1}, "单元素");
        testCase(solution, new int[]{5, 5, 5, 5, 5}, 2, new int[]{5, 5, 5, 5}, "全部相等");
        testCase(solution, new int[]{1, 2, 3, 4, 5, 6}, 3, new int[]{3, 4, 5, 6}, "严格递增");
        testCase(solution, new int[]{9, 8, 7, 6, 5, 4}, 2, new int[]{9, 8, 7, 6, 5}, "严格递减");
        testCase(solution, new int[]{-4, -2, -5, -1, -7}, 2, new int[]{-2, -2, -1, -1}, "包含负数");
        testCase(solution, new int[]{2, 1, 3}, 1, new int[]{2, 1, 3}, "k=1 情况");
        testCase(solution, new int[]{2, 1, 3}, 3, new int[]{3}, "k=数组长度");
        testCase(solution, new int[]{1, 3, 1, 2, 0, 5}, 3, new int[]{3, 3, 2, 5}, "重复与波动");
        testCase(solution, new int[]{10000, -10000, 10000, -10000, 10000}, 2, new int[]{10000, 10000, 10000, 10000}, "极值交替");

        // 随机对比测试，保证正确性
        randomCheck(solution, 5, 15, 10, "随机对比验证1");
        randomCheck(solution, 8, 20, 20, "随机对比验证2");

        // 性能（大规模）测试：仅验证不抛异常且结果长度正确
        largeScaleSmokeTest(solution, 100_000, 500, "大规模性能冒烟测试");

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * 基础测试用例：同时验证 O(n) 与 暴力结果一致
     */
    private static void testCase(S46_Hard_239_滑动窗口最大值 sol, int[] nums, int k, int[] expected, String name) {
        System.out.println("--- 测试: " + name + " ---");
        System.out.println("输入数组: " + Arrays.toString(nums) + ", k=" + k);
        int[] fast = sol.maxSlidingWindow(nums, k);
        int[] brute = sol.maxSlidingWindowBruteForce(nums, k);
        System.out.println("单调队列结果:   " + Arrays.toString(fast));
        System.out.println("暴力验证结果:   " + Arrays.toString(brute));
        System.out.println("期望结果:       " + Arrays.toString(expected));
        assert Arrays.equals(fast, expected) : "单调队列结果与期望不符";
        assert Arrays.equals(brute, expected) : "暴力结果与期望不符";
        System.out.println("✓ 用例通过\n");
    }

    /**
     * 进行多组随机数组验证：确保单调队列与暴力实现一致
     *
     * @param maxLen 最大数组长度
     * @param maxVal 数值范围 [-maxVal, maxVal]
     * @param rounds 轮数
     */
    private static void randomCheck(S46_Hard_239_滑动窗口最大值 sol, int maxLen, int maxVal, int rounds, String name) {
        System.out.println("--- 随机测试: " + name + " ---");
        java.util.Random rand = new java.util.Random();
        for (int t = 1; t <= rounds; t++) {
            int len = 1 + rand.nextInt(maxLen); // 长度至少为1
            int k = 1 + rand.nextInt(len); // 1..len
            int[] arr = new int[len];
            for (int i = 0; i < len; i++) {
                arr[i] = rand.nextInt(2 * maxVal + 1) - maxVal; // [-maxVal, maxVal]
            }
            int[] a = sol.maxSlidingWindow(arr, k);
            int[] b = sol.maxSlidingWindowBruteForce(arr, k);
            if (!Arrays.equals(a, b)) {
                System.out.println("随机失败 用例:" + Arrays.toString(arr) + " k=" + k);
                System.out.println("单调队列: " + Arrays.toString(a));
                System.out.println("暴力:     " + Arrays.toString(b));
                throw new AssertionError("随机对比失败");
            }
        }
        System.out.println("✓ 随机测试全部通过\n");
    }

    /**
     * 大规模性能冒烟测试：验证算法在最大约束下的时间表现（不做严格基准，仅做功能性确认）
     */
    private static void largeScaleSmokeTest(S46_Hard_239_滑动窗口最大值 sol, int len, int k, String name) {
        System.out.println("--- 性能测试: " + name + " ---");
        int[] arr = new int[len];
        java.util.Random rand = new java.util.Random(42);
        for (int i = 0; i < len; i++) {
            arr[i] = rand.nextInt(20001) - 10000; // [-10000, 10000]
        }
        long start = System.currentTimeMillis();
        int[] res = sol.maxSlidingWindow(arr, k);
        long duration = System.currentTimeMillis() - start;
        // 结果长度应为 len - k + 1
        assert res.length == len - k + 1 : "结果长度不符合预期";
        System.out.println("结果长度: " + res.length + ", 耗时: " + duration + " ms");
        // 给出前5个结果示例（避免刷屏）
        System.out.println("前5个窗口最大值示例: " + Arrays.toString(Arrays.copyOf(res, Math.min(5, res.length))));
        System.out.println("✓ 性能冒烟测试通过\n");
    }
}
